// 文件名：multiset_bag_counts.cpp
// 目的：演示 std::multiset 作为“多重集合”（bag）的典型用法：
//      - 保留重复元素并按排序遍历；
//      - 计数某元素出现次数；
//      - 通过 equal_range 遍历同值区间；
//      - 按键删除所有指定值，并统计剩余元素的频次直方图。
// 要点：
//   - multiset 按键有序，允许重复值；count(value) 返回重复次数；
//   - equal_range(value) 得到 [first,last) 区间，便于批量遍历同值；
//   - erase(value) 会移除所有等于 value 的元素；
//   - 统计直方图可遍历 multiset 并在 map 中累加计数（或用 unordered_map）。
// 复杂度：
//   - 插入/查找/计数/删除：O(log N) 至 O(k + log N)（k 为重复数）；
//   - 直方图统计：O(N)。

#include <iostream>
#include <map>
#include <set>
#include <string>

int main() {
    // 初始化多重集合：含重复水果名称
    std::multiset<std::string> bag = {
        "apple", "banana", "banana", "date", "apple", "apple", "cherry"
    };

    // 遍历输出：有序并包含重复项
    std::cout << "Bag contents (sorted with duplicates):\n";
    for (const auto& item : bag) {
        std::cout << "  " << item << '\n';
    }

    // 统计指定元素的出现次数
    auto showCount = [&](const std::string& value) {
        std::cout << "Count of \"" << value << "\": " << bag.count(value) << '\n';
    };

    showCount("apple");
    showCount("banana");
    showCount("grape");

    // equal_range：遍历所有 "apple"
    auto [begin, end] = bag.equal_range("apple");
    std::cout << "Apples (range iteration):";
    for (auto it = begin; it != end; ++it) {
        std::cout << ' ' << *it;
    }
    std::cout << '\n';

    // 删除所有 "banana"
    bag.erase("banana");

    // 统计剩余元素的频次直方图
    std::cout << "After removing all bananas, unique counts:\n";
    std::map<std::string, std::size_t> histogram;
    for (const auto& item : bag) {
        ++histogram[item];
    }
    for (const auto& [value, cnt] : histogram) {
        std::cout << "  " << value << " -> " << cnt << '\n';
    }

    return 0;
}